package fina.heap;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

//反向索引表
public class HeapGeator<T> {
   private ArrayList<T> heap;
   private int heapSize;
   private HashMap<T,Integer> indexMap;
   private Comparator<? super T> comp;

    public HeapGeator(Comparator<? super T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }
    public boolean isEmpty(){
        return heapSize == 0;
    }
    public int size(){
        return heapSize;
    }
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    public void remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (obj != replace) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    // 请返回堆上的所有元素
    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    public T peek() {
        return heap.get(0);
    }
    public void heapInsert(int index){
        while(comp.compare(heap.get(index),heap.get((index - 1) / 2)) < 0 ){
            swap(index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public void heapify(int index){
        int left = index * 2 + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && comp.compare(heap.get(left + 1),heap.get(left)) < 0
                    ? left + 1 : left;
            largest = comp.compare(heap.get(largest),heap.get(index)) < 0 ? largest : index;
            if(largest == index){
                break;
            }
            swap(largest,index);
            index = largest;
            left =  index * 2 + 1;
        }

    }
    public void swap(int i,int j){
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i,o2);
        heap.set(j,o1);
        indexMap.put(o1,j);
        indexMap.put(o2,i);
    }
}
